package com.hyb.algorithm.data.struct.dp;

/**
 * @Author: huyanbing
 * @Date: 2021/9/10 2:23 下午
 * <p>
 * 42. 接雨水
 * <p>
 * https://leetcode-cn.com/problems/trapping-rain-water/
 * <p>
 * <p>
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Trap {


    public static void main(String[] args) {

        Trap trap = new Trap();

        int[] height = new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int res = trap.trap(height);

        System.out.println(res);
    }


    public int trap(int[] height) {

        int n = height.length;

        //备忘录
        int[] leftMax = new int[height.length];
        int[] rightMax = new int[height.length];

        //初始化base
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];

        //先找到左边最大值
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }

        //先找到右边最大值
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }

        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            res += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return res;
    }


    public int trap1(int[] height) {

        int n = height.length;
        int res = 0;
        for (int i = 1; i < n - 1; i++) {
            int leftMax = 0;
            int rightMax = 0;
            //右边的最大值
            for (int j = i; j < n; j++) {
                leftMax = Math.max(leftMax, height[j]);
            }

            //左边的最大值
            for (int h = 0; h <= i; h++) {
                rightMax = Math.max(rightMax, height[h]);
            }
            res += Math.min(leftMax, rightMax) - height[i];
        }

        return res;
    }
}
